write a program to sort a list using insertion sort in python

 

Insertion Sort in Python

The Insertion sort is a straightforward and more efficient algorithm than the previous bubble sort algorithm. The insertion sort algorithm concept is based on the deck of the card where we sort the playing card according to a particular card. It has many advantages, but there are many efficient algorithms available in the data structure.

Python Program

1. # creating a function for insertion  
2. def insertion_sort(list1):  
3.   
4.         # Outer loop to traverse through 1 to len(list1)  
5.         for i in range(1, len(list1)):  
6.   
7.             value = list1[i]  
8.   
9.             # Move elements of list1[0..i-1], that are  
10.             # greater than value, to one position ahead  
11.             # of their current position  
12.             j = i - 1  
13.             while j >= 0 and value < list1[j]:  
14.                 list1[j + 1] = list1[j]  
15.                 j -= 1  
16.             list1[j + 1] = value  
17.         return list1  
18.             # Driver code to test above  
19.   
20. list1 = [10, 5, 13, 8, 2]  
21. print("The unsorted list is:", list1)  
22.   
23. print("The sorted list1 is:", insertion_sort(list1))  

Output:

The unsorted list is: [10, 5, 13, 8, 2]
The sorted list1 is: [2, 5, 8, 10, 13]

Explanation:

In the above code, we have created a function called insertion_sort(list1). Inside the function -

• We defined for loop for traverse the list from 1 to len(list1).
• In for loop, assigned a values of list1 in value Every time the loop will iterate the new value will assign to the value variable.
• Next, we moved the elements of list1[0…i-1], that are greater than the value, to one position ahead of their current position.
• Now, we used the while to check whether the j is greater or equal than 0, and the value is smaller than the first element of the list.
• If both conditions are true then move the first element to the 0^th index and reduce the value of j and so on.
• After that, we called the function and passed the list and printed the result.

The Concept of Insertion Sort

The array spilled virtually in the two parts in the insertion sort - An unsorted part and sorted part.

The sorted part contains the first element of the array and other unsorted subpart contains the rest of the array. The first element in the unsorted array is compared to the sorted array so that we can place it into a proper sub-array.

It focuses on inserting the elements by moving all elements if the right-side value is smaller than the left side.

It will repeatedly happen until the all element is inserted at correct place.

To sort the array using insertion sort below is the algorithm of insertion sort.

• Spilt a list in two parts - sorted and unsorted.
• Iterate from arr[1] to arr[n] over the given array.
• Compare the current element to the next element.
• If the current element is smaller than the next element, compare to the element before, Move to the greater elements one position up to make space for the swapped element.

Let's understand the following example.

We will consider the first element in the sorted array in the following array.

[10, 4, 25, 1, 5]

The first step to add 10 to the sorted subarray

[10, 4, 25, 1, 5]

Now we take the first element from the unsorted array - 4. We store this value in a new variable temp. Now, we can see that the 10>4 then we move the 10 to the right and that overwrite the 4 that was previously stored.

[10, 10, 25, 1, 5] (temp = 4)

Here the 4 is lesser than all elements in sorted subarray, so we insert it at the first index position.

[4, 10, 25, 1, 5]

We have two elements in the sorted subarray.

Now check the number 25. We have saved it into the temp variable. 25> 10 and also 25> 4 then we put it in the third position and add it to the sorted sub array.

[4, 10, 25, 1, 5]

Again we check the number 1. We save it in temp. 1 is less than the 25. It overwrites the 25.

[4, 10, 25, 25, 5] 10>1 then it overwrites again

[4, 25, 10, 25, 5]

[25, 4, 10, 25, 5] 4>1 now put the value of temp = 1

[1, 4, 10, 25, 5]

Now, we have 4 elements in the sorted subarray. 5<25 then shift 25 to the right side and pass temp = 5 to the left side.

[1, 4, 10, 25, 25] put temp = 5

Now, we get the sorted array by simply putting the temp value.

[1, 4, 5, 10, 25]

The given array is sorted.